package code1.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * 原题链接：https://leetcode.cn/problems/two-sum/
 */
public class P1 {

    //暴力法，时间复杂度为0(n^2)
    public int[] twoSum(int[] nums, int target) {
        int[] res=new int[2];
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    res[0]=i;
                    res[1]=j;
                    return res;
                }
            }
        }
        return res;
    }

    //利用hash表
    public int[] twoSum2(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<>();       //若key为nums[i],则value为i
        for(int i=0;i<nums.length;i++){
            if(map.get(target-nums[i])!=null){
                int[] res=new int[2];
                res[0]=map.get(target-nums[i]);
                res[1]=i;
                return res;
            }else{
                map.put(nums[i],i);
            }
        }
        return null;
    }
}
